//不同子序列数量，例如：s = "rabbbit", t = "rabbit"，有3个
public class DiffChildrenSeq {
}
class DiffChildrenSeqSolution {
    public int numDistinct(String s, String t) {
        char[] chas = s.toCharArray();
        char[] chat = t.toCharArray();
        int ns = chas.length;
        int nt = chat.length;
        int[][] dp = new int[ns+1][nt+1];
        for(int i=0;i<=ns;i++)
            dp[i][0] = 1;
        for(int i=1;i<=ns;i++){
            for(int j=1;j<=nt;j++){
                dp[i][j] = dp[i-1][j];
                if(chas[i-1]==chat[j-1]){
                    dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
                }
            }
        }
        return dp[ns][nt];
    }
}